Binary search tree to greater sum tree [DFS]

Time: O(N); Space: O(H); medium

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.

• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = {TreeNode} [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

Output: {TreeNode} [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Constraints:

• The number of nodes in the tree is between 1 and 100.

• Each node will have value between 0 and 100.

• The given tree is a binary search tree.

Note:

• This question is the same as https://leetcode.com/problems/convert-bst-to-greater-tree/

Hints:

1. What traversal method organizes all nodes in sorted order?

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Auxiliary Tools

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. Depth First Search

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def bstToGst(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def bstToGstHelper(root, prev):
            if not root:
                return root
            bstToGstHelper(root.right, prev)
            root.val += prev[0]
            prev[0] = root.val
            bstToGstHelper(root.left, prev)
            return root

        prev = [0]
        return bstToGstHelper(root, prev)

s = Solution1()

root = TreeNode(4)
root.left, root.right = TreeNode(1), TreeNode(6)
root.left.left, root.left.right = TreeNode(0), TreeNode(2)
root.right.left, root.right.right = TreeNode(5), TreeNode(7)
root.left.right.right = TreeNode(3)
root.right.right.right = TreeNode(8)
tree = s.bstToGst( root)
t = TreeTasks()
dot = t.visualize_tree(tree)

See also:

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree

Related problems:

https://leetcode.com/problems/convert-bst-to-greater-tree/